#ifndef PRVP_INITIALSOLUTION_Savings_HPP_
#define PRVP_INITIALSOLUTION_Savings_HPP_

#include "../OptFrame/InitialSolution.h"
#include "../OptFrame/Util/TestSolution.hpp"

#include "ProblemInstance.hpp"

#include "Representation.h"
#include "Solution.h"

#include "Evaluator.hpp"

#include <list>

#include <algorithm>
#include <stdlib.h>

#define EXT1 4
#define EXT2 5

using namespace std;

class PRVPInitialSolutionSavings: public InitialSolution<RepPRVP>
{
private:
	PRVPProblemInstance& pPRVP;
	RandGen& rg;

	//heurística construtiva Savings de Clarke and Wright
	RepPRVP* savings(vector<vector<int> >& LC, Matrix<double>* dist, vector<int>* loads, double capVehicle)
	{
		/*
		 tabela auxiliar, mantem os seguintes dados:
		 # da rota, custo, demanda atendida, # de clientes, extremo 1, extremo 2
		 */
		vector<vector<double> >* t; //tabela auxiliar por rota

		//lista de clientes que estão em cada uma das rotas
		vector<vector<int> > cs; // clientes por rota

		//ls:  vetor(valor da economia, [i,j] ) -> valor da economia ao ligar i com j
		vector<pair<double, pair<int, int> > > ls;

		//mapeamento que identifica em qual rota está cada cliente
		map<int, int> rotaCliente;

		RepPRVP* retorno = new RepPRVP;

		//executando o algoritmo Savings para cada periodo
		for (int p = 0; p < LC.size(); p++)
		{
			//criando a tabela auxiliar
			t = new vector<vector<double> > ;
			//zerando o vetor de clientes
			cs.clear();
			//zerando as rotas associadas a cada cliente
			rotaCliente.clear();
			//zerando a lista de savings
			ls.clear();
			//vetor auxiliar para a criação da tabela
			vector<double> aux;
			//lista das rotas que não serão mais utilizadas
			vector<int> deleteList;

			//completando os dados da tabela auxiliar para cada uns dos clientes
			for (int c = 0; c < LC.at(p).size(); c++)
			{
				aux.clear();
				aux.push_back(c); // identificador da rota
				aux.push_back(2 * (*dist)(0, LC.at(p).at(c))); //custo de ir do depósito ao cliente e do cliente ao depósito
				aux.push_back(loads->at(LC.at(p).at(c))); // demanda do cliente
				aux.push_back(1); // número de clientes para essa rota
				aux.push_back(LC.at(p).at(c)); // primeiro extremo da rota
				aux.push_back(LC.at(p).at(c)); // segundo extremo da rota
				//adicionando os valores à tabela
				t->push_back(aux);
				//adicionando esse cliente a lista de clientes por rota
				vector<int> aux2;
				aux2.clear();
				aux2.push_back(LC.at(p).at(c));
				cs.push_back(aux2);
				//adicionando em qual rota está cada cliente
				rotaCliente[LC.at(p).at(c)] = c;
			}
			//calculando a lista de savings
			double saving;
			pair<double, pair<int, int> > laux;
			pair<int, int> valor_aux;

			//caminhando por todas as rotas presentes na tabela auxiliar de rotas
			for (int r1 = 0; r1 < t->size() - 1; r1++)
			{
				for (int r2 = r1 + 1; r2 < t->size(); ++r2)
				{
					//calculo da economia
					saving = (*dist)(t->at(r1).at(EXT1), 0) + (*dist)(0, t->at(r2).at(EXT1)) + (*dist)(t->at(r1).at(EXT1), t->at(r2).at(EXT1));
					//adicionando esse valor a lista de savings
					valor_aux.first = t->at(r1).at(EXT1);
					valor_aux.second = t->at(r2).at(EXT1);
					laux.first = saving;
					laux.second = valor_aux;
					ls.push_back(laux);
				}

			}

			//ordenando a lista de savings
			sort(ls.begin(), ls.end(), comparacaoSavings);

			//fazendo os merges pela lista de savings
			//enquanto existir elementos na lista e o valor da economia for diferente de 0
			int c1, c2, rc1, rc2, extc1, extc2;
			while ((!ls.empty()) && ls.at(0).first >= 0)
			{

				//retirando a economia
				saving = ls.at(0).first;
				//retirando os clientes
				c1 = ls.at(0).second.first;
				c2 = ls.at(0).second.second;
				//rotas desses clientes
				rc1 = rotaCliente[c1];
				rc2 = rotaCliente[c2];

				//verificando se respeita a restrição de carga
				if (t->at(rc1).at(2) + t->at(rc2).at(2) <= capVehicle)
				{
					//verificando se os dois clientes são extremos
					if (clienteExtremo(c1, t) && clienteExtremo(c2, t))
					{
						//verificando se não estão na mesma rota
						if (rc1 != rc2)
						{

							//quatro casos de merge dependendo de qual extremo está cada cliente
							//extremo do cliente 1 - recebe o valor 1 se estiver no primeiro extremo, e 2 caso contrário
							extc1 = t->at(rc1).at(EXT1) == c1 ? 1 : 2;
							//extremo do cliente 2 - recebe o valor 1 se estiver no primeiro extremo, e 2 caso contrário
							extc2 = t->at(rc2).at(EXT1) == c2 ? 1 : 2;

							//primeiros dois casos - clientes como extremos diferentes
							if (extc1 != extc2)
							{
								if (extc1 == 2) //primeiro caso, o cliente 1 está no segundo extremo
								{
									//realizando o merge
									mergeSavings(saving, rc1, rc2, &rotaCliente, t, &cs, &deleteList);

								}
								else // segundo caso, o cliente 1 está no primeiro extremo, logo o cliente 2 está no segundo
								{
									//realizando o merge
									mergeSavings(saving, rc2, rc1, &rotaCliente, t, &cs, &deleteList);
								}
							}
							else //outros dois casos, clientes com mesmos extremos
							{
								if (extc1 == 1) //primeiro caso, caso ambos sejam o primeiro extremo
								{
									//realizando o merge
									//invertendo a rota do cliente 1, logo o extremo tb deve invertido
									reverse(cs.at(rc1).begin(), cs.at(rc1).end());
									int aux = t->at(rc1).at(EXT1);
									t->at(rc1).at(EXT1) = t->at(rc1).at(EXT2);
									t->at(rc1).at(EXT2) = aux;
									mergeSavings(saving, rc1, rc2, &rotaCliente, t, &cs, &deleteList);
								}
								else //segundo caso, ambos no segundo extremo
								{
									//realizando o merge
									// invertendo a rota do cliente 2, logo o extremo tb deve ser invertido
									reverse(cs.at(rc2).begin(), cs.at(rc2).end());
									int aux = t->at(rc2).at(EXT1);
									t->at(rc2).at(EXT1) = t->at(rc2).at(EXT2);
									t->at(rc2).at(EXT2) = aux;
									mergeSavings(saving, rc1, rc2, &rotaCliente, t, &cs, &deleteList);
								}

							}
						}

					}

				}

				//removendo o saving já processado, que é sempre o primeiro da lista
				ls.erase(ls.begin());

			}

			//removendo as rotas que não serão mais utilizadas
			sort(deleteList.begin(), deleteList.end());

			for (int i = 0; i < deleteList.size(); i++)
			{
				cs.erase(cs.begin() + deleteList.at(i) - i);
			}

			//adicionando as rotas geradas a representacao da solucao
			retorno->push_back(cs);

		}

		delete t;
		return retorno;
	}

	//retorno se o cliente é um dos extremos no algoritmo Savings
	bool clienteExtremo(int c, vector<vector<double> >* t)
	{
		bool extremo = false;

		for (int i = 0; i < t->size() && !extremo; i++)
		{
			extremo = (t->at(i).at(EXT1) == c) || (t->at(i).at(EXT2) == c);
		}
		return extremo;
	}

	//metodo que une duas rotas já atualizando todos os valores da tabela auxiliar
	void mergeSavings(double saving, int rc1, int rc2, map<int, int> * rotaCliente, vector<vector<double> >* t, vector<vector<int> >*cs, vector<int>* deleteList)
	{
		cs->at(rc1).insert(cs->at(rc1).end(), cs->at(rc2).begin(), cs->at(rc2).end());
		//atualizando a tabela auxiliar
		//custo
		t->at(rc1).at(1) = t->at(rc1).at(1) + t->at(rc2).at(1) - saving;
		// demanda atendida
		t->at(rc1).at(2) += t->at(rc2).at(2);
		// número de clientes
		t->at(rc1).at(3) += t->at(rc2).at(2);
		// segundo extremo da rota do cliente 1, que deixa de ser esse segundo extremo
		t->at(rc1).at(EXT2) = t->at(rc2).at(EXT2);

		//alterando em qual rota está cada cliente
		for (int i = 0; i < cs->at(rc2).size(); i++)
		{
			rotaCliente->at(cs->at(rc2).at(i)) = rc1;
		}
		//removendo a rota que foi unida
		deleteList->push_back(rc2);
	}

	/*
	 * essa função decompoe a opção escolhida representada por um inteiro
	 * em um vetor com os periodos que essa escolha representa
	 */
	vector<int> decompoeEscolha(int escolha)
	{
		vector<int> periodos;
		int p = pPRVP.nPeriod - 1;
		while (escolha != 0)
		{
			if (escolha % 2 == 1)
			{
				periodos.push_back(p);
			}
			escolha = escolha / 2;
			p--; //passando para o proximo periodo
		}

		return periodos;
	}

	//funcao que verifica se a capacidade máxima para um periodo foi superada
	bool ultrapassaQ(vector<int>& qAtualPP, int qMaxPP, int demanda, vector<int>& periodos)
	{
		bool ultrapassou = false;

		for (int i = 0; i < periodos.size() && !ultrapassou; i++)
		{
			ultrapassou = qAtualPP.at(periodos.at(i)) + demanda > qMaxPP;
		}
		return ultrapassou;
	}

	//método para realizar a ordenação dos dados da lista de Savings
	static bool comparacaoSavings(pair<double, pair<int, int> > a, pair<double, pair<int, int> > b)
	{
		return (a.first < b.first);
	}

	//método para realizar a ordenação dos dados pelo número de combinações
	static bool comparacao(vector<int> a, vector<int> b)
	{
		return (a.at(NCOMB) < b.at(NCOMB));
	}

	vector<vector<int> >& CriaLC()
	{
		vector<vector<int> >* LC = new vector<vector<int> > (pPRVP.nPeriod);
		vector<int> qAtualPP(pPRVP.nPeriod, 0); // capacidade atual do periodo, iniciado com 0
		int qMaxPP = pPRVP.nVeic * pPRVP.capacidade; //capacidade máxima que um periodo pode atender
		int nComb; //número de combinações possíveis
		int escolha; //combinação escolhida
		vector<int> periodos; //periodos representados pela escolha

		//criando os dados adicionais para serem manipulados sem alterar os dados originais
		vector<vector<int> > dadosAdd = *pPRVP.dados;

		//ordenando os cliente por menor número de opções de periodos disponíveis
		sort(dadosAdd.begin(), dadosAdd.end(), comparacao);
		//for inicia de 1 (um) para descartar o Depósito (posicao 0)
		for (unsigned int i = 1; i < dadosAdd.size(); ++i) //for do número de clientes
		{
			nComb = dadosAdd.at(i).at(NCOMB);
			int c = 0;
			do
			{
				c++;
				if (c > 5 * nComb)
				{
					//não está conseguindo continuar, reseta o método
					delete LC;
					LC = new vector<vector<int> > (pPRVP.nPeriod);
					for (int j = 0; j < qAtualPP.size(); j++)
						qAtualPP.at(j) = 0;
					nComb = dadosAdd.at(1).at(NCOMB);
					i = 1;
				}
				escolha = dadosAdd.at(i).at(5 + (rg.rand() % nComb));
				periodos = decompoeEscolha(escolha);
			} while (ultrapassaQ(qAtualPP, qMaxPP, dadosAdd.at(i).at(DEMANDA), periodos));

			pPRVP.escolhas->at(dadosAdd.at(i).at(0)) = escolha;
			pPRVP.periodsCli->at(dadosAdd.at(i).at(0)).clear();

			for (int p = 0; p < periodos.size(); ++p)
			{
				//atualizando a capacidade atual que o periodo está atendendo
				qAtualPP.at(periodos.at(p)) += dadosAdd.at(i).at(DEMANDA);
				//adicionando o cliente
				LC->at(periodos.at(p)).push_back(dadosAdd.at(i).at(0));
				//adicionando os periodos escolhidos no problema teste
				pPRVP.periodsCli->at(dadosAdd.at(i).at(0)).push_back(periodos.at(p));
			}

		}

		/* Verificando se a restrição de capacidade foi atendida
		 * for(int i = 0 ; i < qAtualPP.size(); i ++)
		 {
		 cout<<"Periodo "<<i<<endl;
		 cout<<"\t qAtual: "<<qAtualPP.at(i)<<" < "<<qMaxPP<<endl;

		 }*/

		return *LC;

	}

public:

	PRVPInitialSolutionSavings(PRVPProblemInstance& _pPRVP, RandGen& _rg) : // If necessary, add more parameters
		pPRVP(_pPRVP), rg(_rg)
	{
	}

	~PRVPInitialSolutionSavings()
	{}

	SolutionPRVP& generateSolution()
	{
		RepPRVP* newRep;

		//gerando vetor de demandas
		vector<int> demandas;

		for (int i = 0; i < pPRVP.dados->size(); i++)
		{
			demandas.push_back(pPRVP.dados->at(i).at(DEMANDA));
		}

		newRep = savings(CriaLC(), pPRVP.dist, &demandas, pPRVP.capacidade);
		int num_tentativas = 0;
		//verificando se não está ultrapassando o número de veículos
		for (int p = 0; p < newRep->size(); p++)
		{
			if (newRep->at(p).size() > pPRVP.nVeic)
			{
				//caso gere solução inviável, outra solução inicial é gerada
				newRep = savings(CriaLC(), pPRVP.dist, &demandas, pPRVP.capacidade);
				num_tentativas++;
				p = 0;
			}
			if(num_tentativas > 100)
			{
				break;
			}

		}

		//adicionando rotas vazias qdo necessario
		for (int p = 0; p < newRep->size(); p++)
		{
			for (int r = 0; r < pPRVP.nVeic - newRep->at(p).size(); r++)
				newRep->at(p).push_back(vector<int> ());
		}

		return *new TestSolution<RepPRVP> (*newRep);
	}

};

#endif /*PRVP_INITIALSOLUTION_Savings_HPP_*/
